package 算法.其他算法;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;

/**
 * 找出字符流中第一个只出现一次的字符。
 */
public class JZ75字符流中第一个不重复的字符 {
    //Insert one char from stringstream
    //哈希表+字符串
    private StringBuilder s = new StringBuilder();
    private HashMap<Character, Integer> mp = new HashMap<>();
    public void Insert(char ch)
    {
        //插入字符
        s.append(ch);
        //哈希表记录字符出现次数
        mp.put(ch, mp.getOrDefault(ch, 0) + 1);
    }
    //return the first appearence once char in current stringstream
    public char FirstAppearingOnce()
    {
        //遍历字符串
        for(int i = 0; i < s.length(); i++)
            //找到第一个出现次数为1的
            if(mp.get(s.charAt(i)) == 1)
                return s.charAt(i);
        return  '#';
    }

    //哈希表+队列
    private Queue<Character> q = new LinkedList<>();
    private HashMap<Character, Integer> map = new HashMap<>();
    public void Insert2(char ch)
    {
        //插入字符
        if(!mp.containsKey(ch))
            q.offer(ch);
        //哈希表记录字符出现次数
        map.put(ch, map.getOrDefault(ch, 0) + 1);
    }
    //return the first appearence once char in current stringstream
    public char FirstAppearingOnce2()
    {
        while(!q.isEmpty()){
            //第一个不重复的字符
            if(map.get(q.peek()) == 1)
                return q.peek();
            else
                q.poll();
        }
        return '#';
    }
}
